function testSgAlgo()
     N=1000; 
     Tsize=5;
     m=3;
     uncertaintyLevel=0.6;
     payoffIntervalMatrix=genertatePayoffVariables(Tsize, uncertaintyLevel);
     
     [finalC_ISG, finalPayoff_ISG] = calcISG(payoffIntervalMatrix, m)
     [finalC_InterSG, finalPayoff_InterSG] = calcIntervalSG(payoffIntervalMatrix, m)
     
     
     Carr=zeros(Tsize,N);
     midArr=zeros(1,N);
     for i=1:N
         payoffMatrix = reduceIntervals(payoffIntervalMatrix);
         [finalC, finalPayoff] = calcSG(payoffMatrix, m);
         Carr(:,i)=finalC; midArr(i)=finalPayoff;
     end
    
    
    C
    
    
    plotDecApproximation(Carr, midArr,finalC_ISG, finalPayoff_ISG );
   finalPayoff_ISG 
    % plot(C);
     %midPoint
    
    
    
    
    function [finalC, finalPayoff] = calcSG(payoffMatrix, m)
       targets=payoffMatrix(1,:);
       Uud    =payoffMatrix(2,:);
       Ucd    =payoffMatrix(3,:);
       Uua    =payoffMatrix(4,:); 
       Uca    =payoffMatrix(5,:);
       finalPayoff=0;
       e=0.05;
       Tsize=length(targets);
       C=zeros(Tsize,1);
       maxPayoff=0;
       minPayoff=min(Uud);
       while (maxPayoff-minPayoff)>e 
           midPoint=maxPayoff+(minPayoff-maxPayoff)/2;
           [ret,C]=feasibilityCheck(midPoint,m,C);
           if strcmp(ret,'true')
               minPayoff=midPoint;
               finalPayoff=midPoint;
               finalC=C;
           else
               maxPayoff=midPoint; 
           end
       end
       
       
       
       function [ret,C]=feasibilityCheck(midPoint,m,C)
        Tsize=length(C);
        e=0.05;
        c1=zeros(1,Tsize);
        for t=1:Tsize
          c1(t)= get_c1(t);
        end
        for t=1:Tsize
            totalCov=c1(t);
            C(t)=c1(t);
            if C(t)>1
              continue  
            end
            R=get_R(c1(t),t);
            for tj=1:Tsize
                if(t==tj)
                    continue
                end
                c2=get_c2(R,tj);
                minCov=max(min(c1(tj),c2));
                if minCov<0 || minCov>1
                    break
                end
                totalCov=totalCov+minCov;
                C(tj)=minCov;
            end
            if (minCov>=0 && minCov<=1) && totalCov<=m
                ret='true';
                return 
             end
        end
        ret='false';
        return 
        
        function c1=get_c1(t)
                %cash=1-(midPoint-Uud(t))/(Ucd(t)-Uud(t));
                cash=(midPoint-Uud(t))/(Ucd(t)-Uud(t));
                c1=max([0,cash]);        
            end
            function c2=get_c2(R,t)
                upBound=max(Uua(t),Uca(t));
                lowBound=min(Uua(t),Uca(t));
                if R<lowBound 
                    c2=2;
                    return;
                end

                if R>upBound 
                    c2=0;
                    return;
                end
                cash=(R-Uua(t))/(Uca(t)-Uua(t));
                c2=max([0,cash]); 
            end
            function R=get_R(c1,t)
                R=(c1*Uca(t))+((1-c1)*Uua(t)-e);
            end
        end
    end
    function [finalC, finalPayoff] = calcISG(payoffIntervalMatrix, m)
        targets=payoffIntervalMatrix(1,:);
        Uud    =payoffIntervalMatrix(2,:);
        Ucd    =payoffIntervalMatrix(3,:);
        UuaMin =payoffIntervalMatrix(4,:); 
        UuaMax =payoffIntervalMatrix(5,:); 
        UcaMin =payoffIntervalMatrix(6,:);
        UcaMax =payoffIntervalMatrix(7,:); 
        
       C=zeros(Tsize,1);
       maxPayoff=0;
       minPayoff=min(Uud);
       e=0.05;
       while (maxPayoff-minPayoff)>e 
           midPoint=maxPayoff+(minPayoff-maxPayoff)/2;
           %midPoint=(maxPayoff-minPayoff)/2; 
           [ret,C]=feasibilityCheck(midPoint,m,C);
           if strcmp(ret,'true')
                minPayoff=midPoint;
               finalPayoff=midPoint;
               finalC=C;
           else
               maxPayoff=midPoint; 
           end
       end 
       
        function [ret,C]=feasibilityCheck(midPoint,m,C)
        c1=zeros(1,Tsize);
        for t=1:Tsize
          c1(t)= get_c1(t);
        end
        for t=1:Tsize
            totalCov=c1(t);
            C(t)=c1(t);
            if C(t)>1
              continue  
            end
            R=get_R(c1(t),t);
            for tj=1:Tsize
                if(t==tj)
                    continue
                end
                c2=get_c2(R,tj);
                c3=get_c3(R,tj);
                minCov=max([c3,min(c1(t),c2)]);
                if minCov<0 || minCov>1
                    break
                end
                totalCov=totalCov+minCov;
                C(tj)=minCov;
            end
            if (minCov>=0 && minCov<=1) && totalCov<=m
                ret='true';
                return 
             end
        end
        
        ret='false';
        return 
        
        
        function c1=get_c1(t)
            %cash=1-(midPoint-Uud(t))/(Ucd(t)-Uud(t));
            
            cash=(midPoint-Uud(t))/(Ucd(t)-Uud(t));
            c1=max([0,cash]);        
        end
        function c2=get_c2(R,t)
            %cash=1-(R-UuaMax(t))/(UcaMax(t)-UuaMax(t));
            upBound=max(UuaMax(t),UcaMax(t));
            lowBound=min(UuaMax(t),UcaMax(t));
            if R<lowBound 
                c2=2;
                return;
            end
            
            if R>upBound 
                c2=0;
                return;
            end
            cash=(R-UuaMax(t))/(UcaMax(t)-UuaMax(t));
            c2=max([0,cash]); 
        end
        function c3=get_c3(R,t)
            %cash=1-(R-UuaMin(t))/(UcaMin(t)-UuaMin(t));
            upBound=max(UuaMin(t),UcaMin(t));
            lowBound=min(UuaMin(t),UcaMin(t));
            if R<lowBound 
                c3=2;
                return;
            end
            
            if R>upBound 
                c3=0;
                return;
            end
            cash=(R-UuaMin(t))/(UcaMin(t)-UuaMin(t));
            c3=max([0,cash]); 
        end
        function R=get_R(c1,t)
            R=(c1*UcaMin(t))+((1-c1)*UuaMin(t)-e);
        end
    end
    end
    function [finalC, finalPayoff] = calcIntervalSG(payoffIntervalMatrix, m)
        targets=payoffIntervalMatrix(1,:);
        Uud    =payoffIntervalMatrix(2,:);
        Ucd    =payoffIntervalMatrix(3,:);
        UuaMin =payoffIntervalMatrix(4,:); 
        UuaMax =payoffIntervalMatrix(5,:); 
        UcaMin =payoffIntervalMatrix(6,:);
        UcaMax =payoffIntervalMatrix(7,:); 
        
        Uud=[Uud;Uud];
        Ucd=[Ucd;Ucd];
        Uua=[UuaMin;UuaMax];
        Uca=[UcaMin;UcaMax];
        
        
        finalPayoff=0;
       e=0.05;
       Tsize=length(targets);
       C=zeros(2,Tsize);
       maxPayoff=0;
       minPayoff=min(Uud(1,:));
       while (maxPayoff-minPayoff)>e 
           midPoint=maxPayoff+(minPayoff-maxPayoff)/2;
           [ret,C]=feasibilityCheck(midPoint,m,C);
           if strcmp(ret,'true')
               minPayoff=midPoint;
               finalPayoff=midPoint;
               finalC=C;
           else
               maxPayoff=midPoint; 
           end
       end
       
       
       
       function [ret,C]=feasibilityCheck(midPoint,m,C)
        Tsize=length(C);
        e=0.05;
        c1=zeros(2,Tsize);
        for t=1:Tsize
          c1(:,t)= get_c1(t);
        end
        for t=1:Tsize
            totalCov=c1(:,t);
            C(:,t)=c1(:,t);
            if min(C(:,t))>1
              continue  
            end
            R=get_R(c1(:,t),t);
            for tj=1:Tsize
                if(t==tj)
                    continue
                end
                c2=get_c2(R,tj);
                minCov=i_min(c1(:,tj),c2);
                %minCov=max(min(c1(tj),c2));
                if i_compare(minCov,[0,0])==-1 || i_compare(minCov,[1,1])==1
                    break
                end
                totalCov=i_add(totalCov,minCov);
                C(:,tj)=minCov;
            end
            if (min(minCov)>=0 && max(minCov)<=1) && max(totalCov)<=m
                ret='true';
                return 
             end
        end
        ret='false';
        return 
        
        function c1=get_c1(t)
                %cash=1-(midPoint-Uud(t))/(Ucd(t)-Uud(t));
                up=i_remove(midPoint, Uud(:,t));
                dwn=i_remove(Ucd(:,t), Uud(:,t));
                cash=i_divide(up,dwn);
                c1=i_max([0,0],cash);     
            end
            function c2=get_c2(R,t)
                if i_compare(R,Uua(:,t))==-1; 
                    c2=[2,2];
                    return;
                end

                if i_compare(R,Uca(:,t))==1; 
                    c2=[0,0];
                    return;
                end
                up=i_remove(R, Uua(:,t));
                dwn=i_remove(Uca(:,t), Uua(:,t));
                cash=i_divide(up,dwn);
                
                c2=i_max([0,0],cash);
                 
            end
            function R=get_R(c1,t)                
                left=i_multiply(c1,Uca(:,t));
                right=i_multiply(i_remove([1,1],c1),Uua(:,t));
                sum=i_add(left,right);
                R=i_add(sum,[e,e]);
            end
       end
            
        function  rez=i_min(X,Y)
            a=min(X);b=max(X); c=min(Y); d=max(Y);
            rez=[min(a,c); min(b,d)];
        end
        
        function  rez=i_max(X,Y)
            a=min(X);b=max(X); c=min(Y); d=max(Y);
            rez=[max(a,c); max(b,d)];
        end
        
            function rez=i_add(X,Y)
                %[X,Y]=prepare(X,Y);
                a=min(X);b=max(X); c=min(Y); d=max(Y);
                rez=[a+c;b+d];
            end
            function rez=i_remove(X,Y)
                %[X,Y]=prepare(X,Y);
                a=min(X);b=max(X); c=min(Y); d=max(Y);
                rez=[a-d;b-c];
            end
            function rez=i_multiply(X,Y)
               % [X,Y]=prepare(X,Y);
                a=min(X);b=max(X); c=min(Y); d=max(Y);
                rez=[min([a*c,a*d,b*c,b*d]);max([a*c,a*d,b*c,b*d])];
            end
            function rez=i_divide(X,Y)
              %  [X,Y]=prepare(X,Y);
                a=min(X);b=max(X); c=min(Y); d=max(Y);
                rez=[min([a/c,a/d,b/c,b/d]);max([a/c,a/d,b/c,b/d])];
            end
            function [X1,Y1]=prepare(X,Y)
                lenX=length(X);
                lenY=length(Y);
                if lenX==1
                    X1=[X,X];
                else
                    X1=X;
                end
                if lenY==1
                    Y1=[Y,Y];
                else
                    Y1=Y;
                end
                
            end
            
            function rez=i_compare(X,Y)
                a=min(X);b=max(X); c=min(Y); d=max(Y);
                if b<c
                    rez=-1;
                    return;
                end
                if d<a
                    rez=1;
                    return;
                end
                rez=0;
                return;
            end
    end
    
    function initPayoffsVariables()
               Uud=  [-25, -10, -11];
               Ucd=  [-15, -5 , -10];
               Uua=  [15,  14,  16];
               Uca=  [7,   3,   10];
            
               
            %  rsPayoffMatrix=preparePayoffVariables(Uud, Ucd, Uua, Uca);
            %  Uud=  rsPayoffMatrix(3,:);
            %  Ucd=  rsPayoffMatrix(2,:);
            %  Uua=  rsPayoffMatrix(5,:);
            %  Uca=  rsPayoffMatrix(4,:);
               
    end
    function rsPayoffMatrix=preparePayoffVariables(Uud, Ucd, Uua, Uca)
            targets=1:length(Uud);
            payoffMatrix=[targets;Ucd;Uud; Uca;Uua;];
            target_index=1;
            Ucd_index=2;
            Uud_index=3;
            Uca_index=4;
            Uua_index=5;
            bound=max(Uca);
            rPayoffMatrix=payoffMatrix(:,payoffMatrix(Uua_index,:)>bound);
            rsPayoffMatrix=sortrows(rPayoffMatrix',-target_index)';
    end
    function payoffIntervalMatrix=genertatePayoffVariables(N, uncertaintyLevel) 

           %assert uncertaintyLevel in [0,1]
           Ud1=-rand(1,N)*100;
           Ud2=-rand(1,N)*100;

           Ucd=max(Ud1(1,:),Ud2(1,:));
           Uud=min(Ud1(1,:),Ud2(1,:)); 


           Ua1=rand(1,N)*50;
           Ua2=rand(1,N)*50;

           Uca=max(Ua1(1,:),Ua2(1,:));
           Uua=min(Ua1(1,:),Ua2(1,:)); 

           Dist=Uca-Uua;

           uncertaintyCoef=Dist*uncertaintyLevel;

           uncertU=rand(1,N).*uncertaintyCoef;
           uncertC=rand(1,N).*uncertaintyCoef;


           UuaMax=Uua+uncertU+50;
           UuaMin=Uua-uncertU+50;

           UcaMax=Uca+uncertC+50;
           UcaMin=Uca-uncertC+50;
           
           targets=1:N;
           payoffIntervalMatrix=[targets;Uud;Ucd; UuaMin;UuaMax;UcaMin;UcaMax ];
    end
    function payoffMatrix = reduceIntervals(payoffIntervalMatrix)
        targets=payoffIntervalMatrix(1,:);
        Uud    =payoffIntervalMatrix(2,:);
        Ucd    =payoffIntervalMatrix(3,:);
        UuaMin =payoffIntervalMatrix(4,:); 
        UuaMax =payoffIntervalMatrix(5,:); 
        UcaMin =payoffIntervalMatrix(6,:);
        UcaMax =payoffIntervalMatrix(7,:); 
        Uua=getRandomFromInterval(UuaMin,UuaMax);
        Uca=getRandomFromInterval(UcaMin,UcaMax);
        payoffMatrix=[targets;Uud;Ucd; Uua;Uca ];
    end
    function ret=getRandomFromInterval(min, max)
        size= length(min);
        diff=max-min;
        ret=rand(1,size).*diff+min;
    end
    function plotDecApproximation(Carr, midArr,finalC_ISG, finalPayoff_ISG)
    %   unsortedResult=[1:length(midArr); midArr];
     %  sortedResult=sortrows(unsortedResult',-2)';
      % targets=sortedResult(1,:);
      % plot(targets, midArr);
      
       plotCoverageData(Carr, midArr,finalC_ISG, finalPayoff_ISG);
       %f2=figure;
      % movegui(f2,'center')
      % Carr_size=size(Carr);
     %  N=length(Carr(1,:));
      % subplot(611);plot(1:N ,Carr(1,:), 1:N ,finalC_ISG(1)); title('c1')
      % subplot(612);plot(1:N ,Carr(2,:), 1:N ,finalC_ISG(2)); title('c2');
      % subplot(613);plot(1:N ,Carr(3,:), 1:N ,finalC_ISG(3)); title('c3');
      % subplot(614);plot(1:N ,Carr(4,:), 1:N ,finalC_ISG(4)); title('c4');
     %  subplot(615);plot(1:N ,Carr(5,:), 1:N ,finalC_ISG(5)); title('c5');
     %  subplot(616);plot(midArr,  finalPayoff_ISG);    title('profit');
       min(midArr)
       max(midArr)
       finalPayoff_ISG
    end
    function plotCoverageData(Carr, midArr,finalC_ISG, finalPayoff_ISG)
       Carr_size=size(Carr);
       f2=figure;
       movegui(f2,'center')
       subplotNumb=(Carr_size(1)+1)*100+10;
       for i=1:Carr_size(1)
         subplotNumb=subplotNumb+1;
         subplot(subplotNumb);plotCoveragePlot(Carr, finalC_ISG, i);  
       end
       subplotNumb=subplotNumb+1;
       subplot(subplotNumb);
       plot(1:N,midArr,  1:N,finalPayoff_ISG);    title('Total defender payoff distribution');
       
    end
    function plotCoveragePlot(Carr, finalC_ISG, index)
       plot(1:N ,Carr(index,:), 1:N ,finalC_ISG(index)); title(['Coverage distribution for target ' num2str(index) ]);
    end          
end